package q85

func maximalRectangle(matrix [][]byte) int {
	var max int = 0

	for j := 0; j < len(matrix); j++ {
		for i := 0; i < len(matrix[j]); i++ {
			if matrix[j][i] == '0' {
				continue
			}
			tmp := maximalRectangleByIndex(matrix, j, i)
			if tmp > max {
				max = tmp
			}
		}
	}
	return max
}

func maximalRectangleByIndex(matrix [][]byte, i, j int) int {

	//log.Printf("matrix:(%d,%d)",i,j)

	//竖版的最大矩形
	top, bottom := findColumnRange(matrix, i, j)
	//log.Printf("Column:%d-%d",top,bottom)
	cMax := maxColumnArea(matrix, i, j, top, bottom)
	//log.Printf("Max:%d",cMax)

	//查找横版的
	left, right := findRowRange(matrix, i, j)
	//log.Printf("Row:%d-%d",left,right)
	rMax := maxRowArea(matrix, i, j, left, right)
	//log.Printf("Max:%d",rMax)

	//log.Println("-----------")

	if rMax > cMax {
		return rMax
	}
	return cMax
}

//查找纵向的可生成矩形的范围
func findColumnRange(matrix [][]byte, i, j int) (int, int) {

	top := i
	for {
		if top <= 0 {
			break
		} else if matrix[top-1][j] == '1' {
			top--
		} else {
			break
		}
	}

	bottom := i
	for {
		if bottom >= len(matrix)-1 {
			break
		} else if matrix[bottom+1][j] == '1' {
			bottom++
		} else {
			break
		}
	}

	return top, bottom
}

//查找横向的可生成矩形的范围
func findRowRange(matrix [][]byte, i, j int) (int, int) {

	left := j
	for {
		if left <= 0 {
			break
		} else if matrix[i][left-1] == '1' {
			left--
		} else {
			break
		}
	}

	right := j
	for {
		if right >= len(matrix[i])-1 {
			break
		} else if matrix[i][right+1] == '1' {
			right++
		} else {
			break
		}
	}

	return left, right
}

//查找最大的纵向的矩形
func maxColumnArea(matrix [][]byte, i, j int, top, bottom int) int {
	left := j
	for {
		if left <= 0 {
			break
		} else if isUseColumn(matrix, top, bottom, left-1) {
			left--
		} else {
			break
		}
	}

	right := j
	for {
		if right >= len(matrix[i])-1 {
			break
		} else if isUseColumn(matrix, top, bottom, right+1) {
			right++
		} else {
			break
		}
	}
	area := (right - left + 1) * (bottom - top + 1)

	return area
}

//查找最大的横向的矩形
func maxRowArea(matrix [][]byte, i, j int, left, right int) int {
	top := i
	for {
		if top <= 0 {
			break
		} else if isUseRow(matrix, left, right, top-1) {
			top--
		} else {
			break
		}
	}

	bottom := i
	for {
		if bottom >= len(matrix)-1 {
			break
		} else if isUseRow(matrix, left, right, bottom+1) {
			bottom++
		} else {
			break
		}
	}
	area := (right - left + 1) * (bottom - top + 1)

	return area
}

//查找是否可扩展指定纵向的列
func isUseColumn(matrix [][]byte, top, bottom int, row int) bool {
	//log.Printf("column Use:%d-%d,row: %d",top,bottom,row)
	for i := top; i <= bottom; i++ {
		if matrix[i][row] == '0' {
			return false
		}
	}
	return true
}

//查找是否可扩展指定横向的列
func isUseRow(matrix [][]byte, left, right int, column int) bool {
	//log.Printf("row Use:%d-%d,column: %d",left,right,column)
	for i := left; i <= right; i++ {
		if matrix[column][i] == '0' {
			return false
		}
	}
	return true
}
